<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 最长回文子序列
         * 输入：s = "bbbab"
         * 输出：4 
         * 解释：一个可能的最长回文子序列为 "bbbb" 。
         * 
         * 输入：s = "cbbd"
         * 输出：2
         * 解释：一个可能的最长回文子序列为 "bb" 。
         * 
         * dp[i][j]，从i->j之间的最长回文子序列的长度
         * 
        */
        /* 
            时间：O(n * m)
            空间：O(1)
        */
        // 递归的解法
        var longestPalindromeSubseq = function(s) {
            let dp = new Array(s.length + 1).fill(0).map(() => new Array(s.length).fill(0))
            // 初始化
            for (let i = 0; i < s.length; i++) {
                    dp[i][i] = 1
            }
            // 递推遍历
            for (let i = s.length - 1; i >= 0; i--) {
                for (let j = i + 1; j < s.length; j++) {
                    if (s[i] === s[j]) {
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    } else {
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
                    }
                }
            }
            console.log(dp, 'dp');
            return dp[0][s.length - 1]
        };
        console.log(longestPalindromeSubseq('abc'));
        console.log(longestPalindromeSubseq('aaa'));
    </script>
</body>

</html>